package leetcode_jz_offer;

import java.util.*;

/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 **/
public class Num49_丑数 {
    //运用最小堆，先将1入队，不断取出堆顶元素，再将堆顶元素x的2，3，5倍的数都入堆（优先级队列）中。添加时注意去重，重复则不添加（set集合去重），保证取出不重复的第n个丑数
    public int nthUglyNumber(int n) {
        int[] array={2,3,5};
        Set<Long> set=new HashSet<>();
        Queue<Long> queue=new PriorityQueue<>();//优先级队列默认最小堆
        //丑数从1开始
        set.add(1L);
        queue.offer(1L);
        int res=0;//记录第n个丑数
        for (int i = 0; i < n; i++) {
            long cur=queue.poll();//元素1出队列（堆），第1个丑数
            res=(int) cur;
            for (int arr:array){
                long temp=arr*cur;
                if(set.add(temp)){
                    queue.offer(temp);
                }
            }
        }
        return res;
    }
    //动态规划求解
    //https://leetcode.cn/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/
    public int nthUglyNumber1(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }

}
